package zuo.highLevel_7;

/**
 * @Author: Forx
 * @Data: 2021/7/10
 * @Desc: Algorithm - zuo.highLevel_7
 * @Version: v1.0
 */
/**
 * 无序数组中找第K小的数
 * 1.BFPRT
 * 2.快排
 * */

import java.util.Arrays;

/**
 * 给定一个面额,和不同的金币,求能用金币组成给定面额的方式有多少种
 * 金币无限
 * 注意:假如给定3,则有 1,1,1 1,2 3这三种,2,1属于重复组
 *
 * 解:
 *      要保证裂开的顺序是非递减的
 * */

class GETMethods{
    public int getMethods(int limit){
        if(limit < 1){
            return 0;
        }
        return process(1,limit);
    }
    private int process(int pre,int rest){
        if(rest==0){
            return 1;

        }
        if(rest < pre){
            return 0;
        }
        int ways = 0;
        for (int i = pre; i <=rest ; i++) {
            ways+=process(i,rest-i);
        }
        return ways;
    }

    private int process2(int limit){
        int[][] dp = new int[limit+1][limit+1];
        /*
        * ----->rest
        * |
        * |
        * pre
        * */
        //rest==0 return 1; pre==0的情况下没有机会,不可能分的,注意
        for (int i = 1; i <= limit; i++) {
            dp[i][0] = 1;
        }
        //rest < pre return 0
        for (int i = 2; i <= limit; i++) {
            for (int j = 0; j < i-1; j++) {
                dp[i][j+1] = 0;
            }
        }
        //ways+=dp[pre][rest-pre]
        //dp[pre][rest] = ∑dp[i][rest-i](pre<=i<=rest)

//        for (int col = 1; col <= limit; col++) {
//            for (int row = 1; row <=col ; row++) {
//                System.out.print("dp["+row+"]["+col+"]=");
//                for (int i = row; i<=col; i++) {
//                    System.out.print("dp["+i+"]["+(col-i)+"]+");
//                    dp[row][col] += dp[i][col-i];
//                }
//                System.out.println();
//            }
//        }
        //dp[pre][rest] = ∑dp[i][rest-i](pre,pre+1,pre+2...rest)
        //dp[pre-1][rest] = ∑dp[i][rest-i](pre-1,pre,pre+1...rest)
        //dp[pre-1][rest] = dp[pre-1][rest-(pre-1)] + dp[pre][rest]
        //dp[pre][rest] = dp[pre][rest-pre] + dp[pre+1][rest]
        for (int row = 1; row <=limit ; row++) {
            dp[row][row]=1;
        }
        for (int col = 1; col <= limit; col++) {
            for (int row = col-1; row >=1 ; row--) {
                //System.out.print("dp["+row+"]["+col+"]=dp["+row+"]["+(col-row)+"]+dp["+(row+1)+"]["+col+"];");
                dp[row][col] = dp[row][col-row]+dp[row+1][col];
                System.out.println();
            }
        }



        for(int[] arr:dp){
            System.out.println(Arrays.toString(arr));
        }

        return dp[1][limit];
    }
    public void test(){
        System.out.println(getMethods(7));
        System.out.println(process2(7));
    }
}
/**
 *给定一棵二叉树的头节点head,已知所有节点的值都不一样，返回其中最大的且符
 * 合搜索二叉树条件的最大拓扑结构的大小。
 * 拓扑结构：不是子树，只要能连起来的结构都算。
 * 1.不对
 * 中序遍历之后,找到最长有序子序列
 * 怎么找最长有序子序列
 * 不对原因是没理解题意,
 *  假设有如下结构
 *          x
 *         /
 *        /
 *       y
 *      / \
 *  ...    z
 *       ... ...
 *
 * 假如z>x 就不在考虑z的左子树是不是还有节点能加入x的BST,因为z不成立,因此z下面的节点都连不上了
 *
 *
 * */
class MaxBSTSize{

}
/**
 * 给定一个长度为偶数的数组arr,长度记为2*N。前N个为左部分，后N个为右部分。
 * arr就可以表示为{L1,L2,..,Ln,R1,R2,..,Rn},
 * 请将数组调整成{R1,L1,R2,L2,..,Rn,Ln}的样子。
 * 时间复杂度ON
 * 时间复杂度O1
 *
 * ...完美洗牌问题
 * 长度是3^k-1的出发点有1...3^(k-1)
 *  如果长度不是3^k-1那就先找到离这个数最近的长度范围,如
 *  长度是14
 *  1 2 3 4 5 6 7 8 9 10 11 12 13 14
 *  l1 l2 l3 l4 l5 l6 l7 r1 r2 r3 r4 r5 r6 r7
 *  最近的是8
 *  那就先将l1..l4 r1..r4放到一起完成
 *  剩下l5 l6 l7 r5 r6 r7六个
 *  那就将l5 r5 排
 *  ...
 * */


/**
 * 给定一个无序数组
 * 将其排序成
 * [a,b,c,d,e]
 * a < = b = > c < = d >= e...
 * 如果这个数组的长度是偶数,那就先排序,排序之后将前一半的数后后一半的数看做上面那个问题
 * 如果数组长度是奇数,那就不管第一个数
 *
 * */
class Sort{

}



public class HL7 {
    public static void main(String[] args) {
        new GETMethods().test();
    }
}
